The architecture of high-speed multipliers is particularly important in digital systems. Concerning the architecture of such multipliers, progress in the way calculations are performed is a critical factor not only with respect to the mere architecture per se of such multipliers, but also with respect to multiplier accumulators, the internal components of computers, digital filters, and, generally, all operators in which multiple operands are summed.
Initially, cellular multipliers comprising a tree were studied in depth by C. S. Wallace, and this work led to highspeed cellular multipliers being implemented that are referred to as "Wallace tree" multipliers.
In general, such multipliers are split into three parts: a modified Booth encoder; a multiple operand adder or partial product reducer; and a final adder. The most remarkable essential characteristic of a multiplier of this type appears in the operand adder, where N operands are summed as two numbers instead of one as is the usual practice, with this operation being written below as "(N,2) summing". To this end, the (N,2) multiple operand adder is constituted by an arrangement of cells comprising a tree of carry-save adders (a Wallace tree). Such a structure of adders of this type avoids horizontal carry propagation. This structure enables (N,2) summing to be performed very quickly, in a period of time proportional to log.sub.3/2 N. For a more complete description of this type of adder, reference may be made by the article by C. S. Wallace entitled "A suggestion for a fast multiplier" published in IEEE Transactions on Electronic Computers, Vol. 13, pp. 14-17, Feb. 1964.
In theory, Wallace's work opened the way to achieving the bettom limit on the calculation time required for performing (N,2) summing when using carry-save adders.
However, implementing Wallace tree structures is made difficult and inconvenient because of the complex intricate interconnections, and this applies particularly when implementing them with plane topology using very large scale integration (VLSI) techniques in which a plurality of carry-save adders are superposed in a layer arrangement.
For this reason, most integrated circuit manufacturers have preferred (N,2) summing structures that make a regular architecture possible over structures that implement a Wallace tree, thereby accepting a compromise relating to calculation time. The most representative of these various other architectures are the following: an iterative array of carry-save adders described by J. Y. Lee, H. L. Garvin, and C. W. Slayman in an article entitled "A high speed high density silicon 8.times.8 bit parallel multiplier" published in the IEEE Journal of Solid State Circuits, Vol. SC-22, No. 1, pp. 35-40; Zuras-McAllister tree structures described in the article entitled "Balanced delay trees and combinatorial division in VLSI" by D. Zuras and W. H. McAllister published in IEEE Journal of Solid State Circuits, Vol. 21, pp. 814-819, No. 5, October 1986; and so-called "4-2" tree structures described by W. Li, J. Burr, M. Santoro, and M. Horowitz corresponding to U.S. patent application Ser. No. 088 096 filed Aug. 21, 1987. The calculation times of these three structures are respectively proportional to: N, N.sup.1/2, and log(N).
The iterative array of carry-save adders provides the most regular architecture and it requires interconnections between adjacent layers only, however it suffers from the drawback of being the slowest.
Zuras-McAllister tree structures ("ZM trees") require inter-layer interconnections to be provided because the output of a carry-save adder is not connected to the adjacent adder but is connected to other adders. This has the effect of accelerating the calculation process, but at the cost of increasing the area of silicon required for receiving such a structure. It should nevertheless be underlined that the inter-layer inter-connections required by ZM trees are easy to provide and cheap, since only two inter-layer connection conductors are required. The number of inter-layer conductors is defined as a measure of the inter-layer transparency of carry-save adders, and constant transparency tree structures can lead to very compact topography. However, ZM trees diverge quickly from the Wallace limit as the number of operands N increases.
4-2 type trees appear to be particularly adapted to implementing (2.sup.m, 2) summing, and this is very common in many applications. This type of tree can give rise to calculation time proportional to log(N) which is equal or close to the Wallace bottom limit. However, 2(m-2) inter-layer conductors are required, and this gives rise to a rapid growth in the area of silicon required.
More recently, a "p-th root" tree structure for a cellular multiplier has been described in French patent application No. 88 02701. This structure comprises carry-save adders interconnected by 4-input connectors. Although it approaches the Wallace bottom limit for low values of the number of operands N, calculation time is no longer optimum for large numbers of operands.
An object of the present invention is to remedy the abovementioned drawbacks by implementing a cellular multiplier comprising a tree enabling the Wallace bottom limit to be achieved or approached for large numbers of operands, with the calculation time of the tree cellular multiplier of the invention being substantially optimized.
Another object of the present invention is to implement a tree cellular multiplier enabling the number of inter-layer interconnections to be modified in comparison with the number of inter-layer interconnections in ZM tree cellular multipliers, for the purpose of increasing processing speed.